1. Field of the Invention
The present invention relates generally to an apparatus and method for stopping iterative decoding. More particularly, the present invention relates to an apparatus and method for stopping iterative decoding using a cyclic redundancy check (CRC) in a mobile communication system.
2. Description of the Related Art
Mobile communication systems use an encoder and a decoder to correct errors of a forward channel. In such mobile communication systems, data transmission and reception are performed in a wireless environment. In order to effectively correct errors related to noise occurring in a transmission channel and improve the reliability of data transmission, convolutional codes corresponding to trellis codes, and Reed-Solomon (RS) codes corresponding to linear block codes, are typically used. In 1993, Berrou et al. introduced an iterative decoding method and turbo codes exhibiting error correction capability that can approach the theoretical Shannon limit. In a synchronous system of the 3rd generation partnership project 2 (3GPP2) and an asynchronous system of the 3rd generation partnership project (3GPP) serving as 3rd mobile communication systems, turbo codes have been adopted as error correction codes. The turbo codes ensure higher communication reliability than conventionally used convolutional codes.
FIG. 1 illustrates a structure of a conventional turbo decoder. A turbo encoder is provided with two convolutional encoders that are connected parallel to each other. Thus, an interleaver 130 is connected between two constituent decoders 110 and 120 as decoders for two constituent codes. The first constituent decoder 110 receives L(n) representing a log likelihood ratio (LLR) of input information bits and P1(n) representing an LLR of parity bits mapped to the first constituent decoder 110 and then outputs L1(n).
In an iterative decoding process, prior information apr1(n) is added to the L(n) input at an adder prior to the first constituent decoder, and the sum is then input to the first constituent decoder 110. Herein, the prior information apr1(n) is a log ratio between probabilities that an arbitrary information symbol has values of 0 and 1 before an encoding process. In the general encoding theory, it is assumed that the probability of an information symbol of 0 is equal to that of an information symbol of 1. The first prior information apr1(n) has a constant value of 0. However, while the turbo decoder performs the iterative decoding process, external information obtained from one constituent decoder of the turbo decoder is used as prior information for an information symbol to be decoded by the other constituent decoder, such that the prior information apr1(n) no longer has the constant value of 0.
In the first decoding process, apr1(n) becomes 0. The output L1(n) is a soft output LLR related to information bits of the first constituent decoder 110 and is a sum of the input prior information apr1(n), the information bit LLR L(n) and external information ext1(n) added in the decoding process of the first constituent decoder 110. For the decoding process of the second constituent decoder 120, the prior information apr1(n) is subtracted from the output L1(n) at an adder between the first constituent decoder and the interleaver, and the interleaver 130 then performs an interleaving process on the result. Herein, an interleaved sequence is denoted by L(k) using an index k.
The interleaver 130 performs an operation for interleaving a sequence of data such that an output of the first constituent decoder 110 is proper as an input of the second constituent decoder 120 by considering data interleaved between constituent encoders for configuring turbo codes. The second constituent decoder 120 receives an interleaved sequence L(k)+ext1(k) and a parity bit LLR P2(k), and outputs a soft output LLR L2(k) of interleaved information bits.
Then, ext(k), computed by subtracting input prior information L(k) of the second constituent decoder 120 from the output L2(k) of the second constituent decoder 120 at an adder between the first and second constituent decoders, is input to the first constituent decoder 110 through a second deinterleaver 170. At this time, a deinterleaved sequence of ext2(k) becomes ext2(n)=apr1(n).
Accordingly, the first constituent decoder 110 receives the feedback of the prior information apr1(n) from the second constituent decoder 120. The first constituent decoder 110 receives and re-decodes the prior information, the information bits and the parity bits. When the above-described series of processes are repeated, an output LLR related to information bits is improved and a decoding process having a performance approaching the Shannon limit is possible.
The structure of FIG. 1 uses the two constituent decoders 110 and 120. However, when one encoded frame is decoded, the first and second constituent decoders 110 and 120 do not simultaneously operate, and the first and second constituent decoders can be reused in the same hardware since they each have the same structure.
Conventionally, L2(k) is a final output LLR after designated iterative decoding. When this information is deinterleaved in a first deinterleaver 150 after a hard decision process in a hard decision section 140 and is accumulated in an output buffer 160, the decoding process is completed.
However, the turbo codes are constructed in the form of parallel-concatenated convolutional codes in which two recursive systematic convolutional codes are concatenated. When the parallel-concatenated convolutional codes are decoded, one decoding process in which decoding of respective constituent codes is combined is completed. When this decoding process is repeated many times, a decoding performance approaching the Shannon limit can be obtained.
After the discovery of the turbo codes, many codes have been introduced which can obtain a decoding performance approaching the Shannon limit through iterative decoding of serially concatenated convolutional codes, parallel-concatenated block codes, low density parity check (LDPC) codes, repeat accumulate (RA) codes, zigzag codes, and so forth. When the decoder performs an iterative decoding process for codes, there are methods that are capable of stopping the decoding process if the iteration is no longer needed after a sufficient number of iterations.
In the case of LDPC codes, an iterative decoding process is performed using a sum-product algorithm on the basis of a parity check matrix. In the sum-product algorithm, a codeword is identified by parity check at every iterative decoding and the iterative decoding can be stopped. That is, because the sum-product algorithm of the decoding method can identify a codeword in the case of the LDPC codes, stopping criteria can be provided.
In the case of turbo codes of 3GPP2, a cyclic redundancy check (CRC) code is attached to the end of all turbo-coded packets. In an iterative decoding process, a CRC is performed for every hard-decided data. The iterative decoding process is stopped only upon determining that the data is suitable in the CRC.
In the case of turbo codes of 3GPP, Institute of Electrical and Electronics Engineers (IEEE) 802.16, and so forth, a CRC cannot be performed in stopping the iterative decoding process because a CRC region is absent in every frame. Thus, a process for stopping iterative decoding of the turbo codes without additional information uses a hard decision-aided (HDA) method, a cross entropy (CE) method, a method for stopping iterative decoding using a main value such as a minimal value of an LLR during an iterative decoding process for the turbo codes, and so forth.
Among the well-known methods for stopping iterative decoding, the HDA method is superior because the degradation of decoding performance is almost absent and very fast stopping is possible. The CE method needs very complex computations and hardware in actual implementation, and the method using a minimal value of an LLR is inefficient and degrades the performance when automatic gain control is not precise.
Criteria for judging the performance of an iterative decoding stopping scheme include a measurement of performance difference when a predefined maximal iterative decoding process is performed, the average number of iterative decoding processes in a given signal to noise ratio, and so forth. It is preferred that a decoding performance difference is almost absent and that the average number of iterative decoding processes is close to the theoretical limit.
In the iterative decoding stopping scheme, the theoretical limit of the average number of iterative decoding processes is based on a Genie-aided stopping scheme. This scheme stops the iteration when a message to be decoded is equal to a message to be received under an assumption that a receiver already knows the message to be decoded. Because the scheme stops the iteration when data is normally decoded, performance degradation is never present and the average number of iterative decoding processes is minimal. However, the Genie-aided stopping scheme is theoretical, and cannot be actually implemented because the receiver of a communication system cannot know transmitted data. Because the scheme is theoretically an optimal means, it is used as a reference for comparisons between iterative decoding stopping schemes.
In the iterative decoding process for turbo codes, the HDA method stores hard-decided data in each decoding step and compares the stored data with a result of the next decoding step. The HDA method does not affect the decoding performance and is a superior decoding method approaching the theoretical minimum value. In order to implement the HDA method, the decoding process should store information computed by performing a hard decision process for a decoding output of the prior step. Accordingly, the HDA method requires a memory with a size equal to that of the associated information bit length. Further, the HDA method has problems in regard to hardware complexity. These problems will be described in greater detail with reference to FIG. 2.
FIG. 2 is a block diagram illustrating a turbo decoder using the HDA method for iterative decoding of turbo codes. In FIGS. 1 and 2, like reference numerals will be understood to refer to like parts, components and structures, and further description thereof is omitted for clarity and conciseness. In FIG. 2, hard decision results of soft outputs L1(n) and L2(k) from constituent decoders are used as criteria for stopping iterative decoding of the turbo decoder. An exemplary operation of the turbo decoder of FIG. 2 is as follows.
In order to stop iterative decoding using the HDA stopping method, an HDA section 280 uses d1(n) computed by performing a first hard decision process of a first hard decision section 240 for the output L1(n) of the first constituent decoder 110, and d2(n) computed by performing a second hard decision process of the (second) hard decision section 140 for the result of the interleaving process for the output L2(k) of the second constituent decoder 120.
The HDA section 280 receives d1(n) and d2(n) in every constituent decoding. The HDA section 280 stores previously received hard decision information and then outputs a stop signal to a decoder controller 260 if all N inputs including the current input are identical. In response to the stop signal, the decoder controller 260 stops iterative decoding. Herein, the HDA method for stopping iterative decoding when all N decoding frames are identical is referred to as the “N-HDA stopping method”.
The HDA stopping method is superior because performance degradation of the decoder due to the processes for stopping iterative decoding is almost absent, and very fast stopping is possible. However, when a maximal frame size is L bits in the HDA section 280 of FIG. 2, a memory 281 of size NL or (N−1)L bits is required in the case of the N-HDA stopping method.
That is, in the iterative decoding process for turbo codes, the HDA method stores hard-decided data in each decoding step and compares the stored data with a result of the next decoding step. The HDA method does not affect the decoding performance and is a superior decoding method approaching the theoretical minimum value. In order to implement the HDA method, the decoding process should store information computed by performing a hard decision process for a decoding output of the prior step. To do so, the HDA method requires the memory 281 with a size equal to that of the associated information bit length and further has problems in regard to hardware complexity.
Accordingly, a need exists for an improved system and method for efficiently and effectively stopping iterative decoding of turbo codes in a mobile communication system.